package com.example.sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;

public class QuickSort3 {

    public static void quickSort(int[] arr, int startIndex,
                                 int endIndex) throws Exception{
             // 用一个集合栈来代替递归的函数栈
             Stack<Map<String, Integer>> quickSortStack = new
                Stack<Map<String, Integer>>();
             // 整个数列的起止下标，以哈希的形式入栈
             Map rootParam = new HashMap();
             rootParam.put("startIndex", startIndex);
             rootParam.put("endIndex", endIndex);
             quickSortStack.push(rootParam);

             // 循环结束条件：栈为空时
            while (!quickSortStack.isEmpty()) {
                     //  栈顶元素出栈，得到起止下标
                     Map<String, Integer> param = quickSortStack.pop();
                     //  得到基准元素位置
                     int pivotIndex = partition(arr, param.get("startIndex"),
                    param.get("endIndex"));
                     //  根据基准元素分成两部分, 把每一部分的起止下标入栈
                    if(param.get("startIndex") <  pivotIndex -1){
                             Map<String, Integer> leftParam = new HashMap<String,
                        Integer>();

                leftParam.put("startIndex", param.get("startInd"));
                leftParam.put("endIndex", pivotIndex-1);
                quickSortStack.push(leftParam);
            }
            if(pivotIndex + 1 < param.get("endIndex")) {
                Map<String, Integer> rightParam = new HashMap<String, Integer>();
                rightParam.put("startIndex", pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }

    private static class Stack<T> {
        private ArrayList<T> elements;

        public Stack() {
            elements = new ArrayList<>();
        }

        public void push(T element) {
            elements.add(element);
        }

        public T pop() throws Exception {
            if (isEmpty()) {
                throw new RuntimeException("栈为空");
            }
            return elements.remove(elements.size() - 1);
        }

        public T peek() throws Exception {
            if (isEmpty()) {
                throw new RuntimeException("栈为空");
            }
            return elements.get(elements.size() - 1);
        }

        public boolean isEmpty() {
            return elements.isEmpty();
        }

        public int size() {
            return elements.size();
        }
    }

    private static int partition(int[] arr, int startIndex,
                                 int endIndex) {
        // 取第1个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }


    public static void main(String[] args) throws Exception{
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}
